package question.solution29;

import question.SolutionTemplate;

import java.util.PriorityQueue;
import java.util.Queue;

public class Solution29 implements SolutionTemplate {

    public int divide(int dividend, int divisor) {
        if(dividend == 0){
            return 0;
        }
        boolean diviendNegative = dividend < 0;
        boolean divisorNegative = divisor < 0;
        boolean resultNegative = diviendNegative ^ divisorNegative;
        int divisorCount = 0;

        if(dividend == Integer.MIN_VALUE && divisor == Integer.MIN_VALUE){
            return 1;
        }else if(divisor == Integer.MIN_VALUE){
            return 0;
        }else if(dividend == Integer.MIN_VALUE && divisor == -1){
            return Integer.MAX_VALUE;
        }else if(dividend == Integer.MIN_VALUE && divisorNegative){
            dividend = Integer.MAX_VALUE + divisor + 1;
            divisorCount++;
        }else if(dividend == Integer.MIN_VALUE){
            dividend = Integer.MAX_VALUE - divisor + 1;
            divisorCount++;
        }
        dividend = Math.abs(dividend);
        divisor = Math.abs(divisor);
        divisorCount = divisorCount + partQuotient(dividend, divisor);
        return resultNegative? -divisorCount : divisorCount;
    }

    private int partQuotient(int diviend, int divisor){
        if(diviend == 0){
            return 0;
        }
        int increasingDivisor = divisor;
        int divisorCount = 0;
        int carry = diviend - increasingDivisor;
        if(carry >= 0){
            divisorCount = 1;
        }else{
            return 0;
        }
        int previousDivisor = increasingDivisor;
        do{
            increasingDivisor = increasingDivisor + increasingDivisor;
            carry = diviend - increasingDivisor;
            if(carry < 0){
                break;
            }else{
                divisorCount = divisorCount + divisorCount;
                previousDivisor = increasingDivisor;
            }
        }while(true);
        return divisorCount + partQuotient(diviend - previousDivisor, divisor);
    }

    public void test() {
        int result = divide(Integer.MIN_VALUE, 1);
        return;
    }

}
